package com.insa.flopenshop;

import java.util.PriorityQueue;

/**
 * Cette classe permet de r�soudre le probl�me openshop avec une heuristique
 * gloutonne. Cette heuristique prend la premi�re ressource universelle
 * disponible puis dresse les sous t�ches pouvant �tre plac� des la lib�ration
 * de la ressource si il y en a on place la sous tache dont le temps de
 * r�alisation est le plus court. Sinon, on cherche la file suivante qui se
 * lib�re le plus t�t et on r�it�re.
 *
 * @author strokyl
 */
public class HeuristiqueGloutonne implements Solver {

	/**
	 * Politique d'ordre de placement des sous t�ches.
	 */
	private GetTachePlacableOrdonne ordreTachePlacable;
	private boolean debug;

	/**
	 *
	 * @param ordreTachePlacable
	 */
	public HeuristiqueGloutonne(GetTachePlacableOrdonne ordreTachePlacable, boolean debug) {
		this.ordreTachePlacable = ordreTachePlacable;
		this.debug = debug;
	}

	/**
	 *
	 */
	public HeuristiqueGloutonne(boolean debug) {
		this(new GetTachePlacablePlusCourteDabord(), debug);
	}

	@Override
	public Solution solve(Instance instance) {
		return solve(instance, null);
	}

	public Solution solve(Instance instance, Solution solutionDeDepart) {

		/**
		 * Le nombre de sous t�che total qui doit �tre plac� dans la
		 * solution
		 */
		int nombreSousTache = instance.getNumTache()
			* instance.getNumRessourceDedie();

		/**
		 * On initie une solution que l'on va construire au fur et �
		 * mesure
		 */
		Solution solution = solutionDeDepart == null ? new Solution(instance) : solutionDeDepart;
		if(debug && solutionDeDepart != null)
			System.out.println("Solution initiale : " + solution);

		/**
		 * Cette variable correspondra au prochain placement dans la
		 * liste
		 */
		Placement nouveauPlacement;

		/**
		 * Cette variable correspond au placement pr�c�dant le nouveau
		 * placement sur la ressource universelle qu'on a choisi
		 */
		Placement placementPrecedant;

		/**
		 * Cette variable correspond � la prochaine sousTache que l'on
		 * va r�aliser
		 */
		SousTache sousTache;

		/**
		 * Ce tableau permet de savoir si on a d�j� plac� une sous place
		 */
		boolean[][] sousTachesDejaPlace = solutionDeDepart == null ?new boolean[instance.getNumTache()][instance.getNumRessourceDedie()] : solution.getTabTachePlace();
		if(debug && solutionDeDepart != null){
			System.out.println("Taches deja placees : ");
			for(int i = 0 ; i < instance.getNumTache() ; i++){
				System.out.print("[");
				for(int j = 0 ; j < instance.getNumRessourceDedie() ; j++){
					if(j != 0)
						System.out.print(", ");
					System.out.print(sousTachesDejaPlace[i][j]);
				}
				System.out.println("]");
			}
		}

		/**
		 * Liste les sous t�ches que l'on pourra placer � une date donn�
		 * (celle au moment ou une ressource universelle se lib�re)
		 */
		Iterable<SousTache> tachesPossible = null;

		/**
		 * Permet d'obtenir les derniers placements fait sur les
		 * diff�rents files de notre solution partielle Les placements
		 * sont class�s de celui qui se termine au plus t�t � celui qui
		 * se termine au plus tard
		 */
		PriorityQueue<Placement> placements;

		/**
		 * date � laquel on va essay� de placer le prochain placement
		 * oldDate date ancienne ou on a essay� de placer le prochain
		 * placement mais ou n'avait pas plus car il y avait pas de
		 * t�che compatible � cette date et non r�alis�
		 * ressourceUniverselle : ressource universelle lib�r� au moment
		 * de date
		 */
		int date, oldDate, ressourceUniverselle;
		date = -1;
		ressourceUniverselle = -1;
		long start_time = System.currentTimeMillis();
		long end_time = 0;

		/**
		 * Tant que l'on n'a pas plac� toutes les taches
		 */
		for (int nombreSousTachePlace = solution.getNombreSousTachePlace(); nombreSousTachePlace < nombreSousTache; nombreSousTachePlace++) {
			/**
			 * On r�cup�re les derniers placements
			 */
			placements = solution.getPlacementsParOrdreDeFin();

			sousTache = null;
			//tant qu'on a pas trouver de sous tache placable pour data
			//on bouge � la prochaine date du prochain placement qui se lib�re
			date = -1;
			if(debug)
				System.out.println("Taches placees : " + nombreSousTachePlace);
			do {
				placementPrecedant = placements.poll();
				oldDate = date;
				date = placementPrecedant.getDateFin();

				//si le nouveau placement se termine au m�me moment alors on sera dans la m�me situation 
				//qu'avant �a ne sert donc � rien d'explorer ce nouveau placement on passe directement au suivant
				if (oldDate != date) {
					//on r�cup�re la ressource universelle qui vient de se lib�r� � date
					ressourceUniverselle = placementPrecedant.getRessourceUniverselle();
					if(debug)
						System.out.println("Tentative de placement sur RU" + ressourceUniverselle + " apres " + placementPrecedant.getSousTache());

					//on r�cup�re les taches r�alisable � date
					tachesPossible = ordreTachePlacable.getTachePlacable(date, solution);

					//on cherche parmis ces taches (qui sont tri� par ordre croissante de temps de r�alisation)
					//celle qui n'a pas �t� fait
					if(debug)
						System.out.println("Sous Taches possibles :");
					for (SousTache hypSousTache : tachesPossible) {
						if(debug)
							System.out.println(hypSousTache);
						if (!sousTachesDejaPlace[hypSousTache.getTache()][hypSousTache.getRessourceDedie()]) {
							sousTache = hypSousTache;
							if(debug)
								System.out.println("valide");
							break;
						}
					}
					if(debug)
						System.out.println("Choix " + sousTache);
				}
				//si on n'a pas trouv� de tache alors on passe au prochain placement
			} while (sousTache == null);

			nouveauPlacement = new Placement(date, instance, sousTache, ressourceUniverselle);
			sousTachesDejaPlace[sousTache.getTache()][sousTache.getRessourceDedie()] = true;
			solution.ajouterPlacement(nouveauPlacement);
		}
		end_time = System.currentTimeMillis();
		if(debug)
			System.out.println("Solution Trouvee en " + (end_time - start_time) + "ms");

		return solution;
	}

}
